#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
using LL = long long;
const int N = 1e5 + 10, M = 3e5 + 10;

int n, m;
int h[N], e[M], ne[M], w[N], idx;
LL dist[N];
int st[N], cnt[N];
int q[M];

void add(int a, int b, int c){
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c;
    h[a] = idx ++;
}


bool spfa(){
    memset(dist, -0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    memset(cnt, 0, sizeof cnt);
    int tt = 1, hh = 0;
    dist[0] = 0;
    st[0] = true;
    q[0] = 0;

    while(hh != tt){
        int t = q[--tt];
        st[t] = false;
    

        for(int i = h[t]; ~i; i = ne[i]){
            int j = e[i];
            if(dist[j] < dist[t] + w[i]){
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if(cnt[j] >= n + 1) return false;
                if(!st[j]){
                    st[j] = true;
                    q[tt++] = j;
                    
                }
            }
        }
    }
    return true;
    

}


int main(){

    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);

    for(int i = 0; i < m; i ++){
        int a, b, p;
        scanf("%d%d%d", &p, &a, &b);

        if(p == 1){
            add(a, b, 0);
            add(b, a, 0);
        }else if(p == 2){
            add(a, b, 1);
        }else if(p == 3){
            add(b, a, 0);
        }else if(p == 4){
            add(b, a, 1);
        }else{
            add(a, b, 0);
        }
    }

    for(int i = 1; i <= n; i ++){
        add(0, i, 1);
    }

    if(!spfa()){
        printf("-1\n");
    }else{
        LL res = 0;
        for(int i = 1; i <= n; i ++){
            res = (LL)dist[i] + res;
        }

        printf("%lld\n", res);
    }
    return 0;

}